The present invention relates to cryptography and, in particular, to a method and an apparatus for protecting an RSA calculation of an output based on input values by means of the Chinese remainder theorem (CRT).
Modular exponentiation is one of the core calculations for various cryptographic algorithms. One example of a widespread cryptographic algorithm is the RSA cryptosystem.
Let N=p·q be the product of two large input primes p and q. Let also a public exponent e be coprime to φ(N)=(p−1)(q−1), wherein φ(.) denotes Euler's totient function. Thereby the totient φ(.) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n. A corresponding secret exponent to the public exponent e is d=e−1 mod φ(N). For the RSA cryptosystem the output or a signature on an input message M is given byS=M′d mod N,  (1)wherein M′=μ(M) for some deterministic padding function μ. The validity of the output S can be then publicly verified by checking whether Se=μ(M)(mod N), using the public exponent e.
Most implementations of the widely-used RSA cryptosystem rely on the Chinese remainder theorem as this greatly improves the performance in both running time as well as memory requirement. In CRT mode of the RSA cryptosystem, the secret parameters are dp=d mod (p−1), dq=d mod (q−1) and qinv=q−1 mod p. The output S is then computed asS=CRT(Sp,Sg)=Sq+q[qinv(Sp−Sq)mod p],  (2)withSP=M′dp mod p,Sq=M′dq mod q.  (3)
Unfortunately, CRT-based implementations of the RSA cryptosystems are also known to be more sensitive to fault attacks. A single fault in an RSA exponentiation may reveal the two secret input prime factors p, q through a gcd-computation (gcd=greatest common divisor). Differential fault attacks against the RSA cryptosystem with CRT have emerged to one of the most important attack scenarios (not only) against RSA, since the publication of Boneh et al., “On the Importance of Checking Cryptographic Protocols for Faults(Extended Abstract), Eurocrypt 1997, pages 37 to 51. A lot of fault attacks have been described in the meantime. Countermeasures to the fault attacks are as diverse as the fault attacks themselves. The first and best known countermeasure is described in U.S. Pat. No. 5,991,415. This specialist publication suggests using a small random number r and to compute the two half exponentiations, Sp and Sq of equations (3) in a redundant way, that isSp*=M′d mod rp Sq*=M′d mod rq,  (4)and to return the output S=CRT (Sp*. Sq*) mod N in case Sp*=Sq*(mod r) and an error or countermeasure otherwise.
Most of the countermeasures of today work on the principle described in U.S. Pat. No. 5,991,415. Redundancy is introduced into the RSA computation, which is checked at the end of the computation and, based on the success of the tests, the (correct) signature is output or the wrong signature is suppressed.
Another alternative is to base a fault-check on a one- or zero-comparison and, in the case of an inequality, to combine the comparing number with a signature, such that the signature is changed or infected in such a way in case of an error, such that an attacker cannot draw any conclusions on the secret key. In this case, a dedicated error output can be avoided, since a double disturbed signature is output.
In case an attacker is able to disturb the check as well, he might be able to suppress the error output or the infection of the signature. For this reason, also the fault revealing parts of the algorithms have to be protected. This is not always an easy task, since it is not possible to know every possible fault attack (used in the future). Due to the diverse fault attacks, additional fault-checks have been added to the algorithms. Each of those fault-checks is a potential target for an attack and has to be carefully protected. For this reason, an RSA cryptosystem might become more and more complex related to a security evaluation, since it has to be secured that the fault-checks cover the whole computation seamlessly.
Hence, it would be desirable to secure the whole critical computation of an RSA-CRT cryptosystem by using as few fault-checks as possible.